package leetcode;

public class Day34 {
    //插入排序
    //时间复杂度O(n^2)
    //空间复杂度O(n)
    public void insert(int[] arr){
        for (int i=1;i<arr.length;i++){
            int tmp=arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if(arr[j]>arr[i]){
                    arr[j+1]=arr[j];
                }
            }
            arr[j+1]=tmp;
        }
    }
    public void swap(int i,int j,int[] arr){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    //希尔排序
    //时间复杂度O(n^2)
    //空间复杂度O(n)
    public int[] shellsort(int[] arr){
        int gap=arr.length;
        while (gap>1){
            gap=gap/2;
            shell(arr,gap);
        }
        return arr;
    }
    public void shell(int[] arr,int gap){
        for (int i=gap;i<arr.length;i++){
            int tmp=arr[i];
            int j=i-gap;
            for (;j>=0;j-=gap){
                if(arr[j]>tmp){
                    arr[j]=arr[j+gap];
                }else break;
            }
            arr[j+gap]=tmp;
        }
    }
    //选择排序
    //时间复杂度O(n^2)
    //空间复杂度O(n)
    public void selectsort(int[] arr){
        for (int i=0;i<arr.length;i++){
            int min=i;
            for (int j=i+1;j< arr.length;j++){
                if (arr[j]<arr[min]){
                    min=j;
                }
            }
            swap(min,i,arr);
        }
    }
    //快速排序
    public void quicksort(int[] arr){
       quick(0,arr.length-1,arr);
    }
    public void quick(int start,int end,int[] arr){
        if (start>=end){
            return;
        }
        int p=hore(start,end,arr);
        quick(start,p,arr);
        quick(p+1,end,arr);
    }
    public int hore(int start,int end,int[] arr){
        int tmp=arr[start];
        int l=start;
        while (start<end){
            while (start<=end&&arr[start]>=tmp){
                start++;
            }
            while (start<=end&&arr[end]<=tmp){
                end--;
            }
            swap(start,end,arr);
        }
        swap(l,start,arr);
        return l;
    }

}
